package day190728;

import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/7/28 上午 10:09
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 去重
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++; // 去重
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--; // 去重
                    }
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

    public int tribonacci(int n) {
        int[] a = new int[38];
        a[0] = 0;
        a[1] = 1;
        a[2] = 1;
        if (n == 0 || n == 1 || n == 2) {
            return a[n];
        }
        for (int i = 3; i < n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n];
    }

    String[] board = {"abcde",
            "fghij",
            "klmno",
            "pqrst",
            "uvwxy",
            "z"};

    public String alphabetBoardPath(String target) {
        StringBuilder result = new StringBuilder();
        char[] chars = target.toCharArray();
        char current = 'a';
        char[][] boardMap = new char[6][5];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].toCharArray().length; j++) {
                boardMap[i][j] = board[i].toCharArray()[j];
            }
        }
        int i = 0;
        int j = 0;
        int k = 0;
        int length = target.length();
        while (true) {
            current = boardMap[i][j];
            if (current == chars[k]) {
                result.append("!");
            }
            if (chars[k] > boardMap[i][j]) {
                if ((i + 1) <= 5 && chars[k] >= boardMap[i + 1][j]) {
                    result.append("D");
                    i++;
                    continue;
                }
                if (chars[k] <= boardMap[i][4]) {
                    result.append("R");
                    j++;
                    continue;
                }
            }
            if (chars[k] < boardMap[i][j]) {
                if ((i - 1) >= 0 && chars[k] <= boardMap[i - 1][k]) {
                    result.append("U");
                    i--;
                    continue;
                }
                if (chars[k] <= boardMap[i][0]) {
                    result.append("L");
                    j--;
                    continue;
                }
            }
            k++;
            if (k >= length) {
                break;
            }
        }
        return result.toString();
    }


    public boolean robot(String command, int[][] obstacles, int x, int y) {
        int xc = 0;
        int yc = 0;
        HashSet<Long> hashSet = new HashSet<>();
        hashSet.add(0L);
        for (int i = 0; i < command.length(); i++) {
            if (command.charAt(i) == 'U') {
                yc++;
            } else {
                xc++;
            }
            hashSet.add((long) (xc << 30 | yc));
        }
        int minTime = Math.min(x / xc, y / yc);
        if (!hashSet.contains((long) (x - minTime * xc) << 30 | (y - minTime * yc))) {
            return false;
        }
        for (int[] obstacle : obstacles) {
            if (obstacle.length < 2) {
                continue;
            }
            if (obstacle[0] > x || obstacle[1] > y) {
                continue;
            }
            minTime = Math.min(obstacle[0] / xc, obstacle[1] / yc);
            if (hashSet.contains((long) (obstacle[0] - minTime * xc) << 30 | (obstacle[1] - minTime * yc))) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ThreeSum threeSum = new ThreeSum();
        System.out.println(threeSum.robot("URR", new int[][]{{40000000, 30000000}}, 30000000, 20000000));
    }

    public int[] fraction(int[] cont) {
        if (cont.length == 0) {
            return new int[]{};
        }
        if (cont.length == 1) {
            return new int[]{cont[0], 1};
        }
        int[] result = new int[2];
        int up = 1;
        int down = cont[cont.length - 1];
        for (int i = cont.length - 2; i > 0; i--) {
            if (cont[i] > 0) {
                up = cont[i] * down + up;
                int gcd = gcd(up, down);
                up /= gcd;
                down /= gcd;
                int temp = up;
                up = down;
                down = temp;
            }
        }
        up = cont[0] * down + up;
        int gcd = gcd(up, down);
        result[0] = up / gcd;
        result[1] = down / gcd;
        return result;
    }

    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

    public int domino(int n, int m, int[][] broken) {
        int[] a = new int[10];
        int[][] f = new int[10][256];
        int ans = 0, i, j, k;
        int[] o = new int[256];
        for (int[] b : broken) {
            a[b[0]] |= 1 << b[1];
        }
        for (int[] ints : f) {
            Arrays.fill(ints, 128);
        }
        f[0][(1 << m) - 1] = 0;
        for (i = 1; i < 1 << m; i++) {
            o[i] = o[i >> 1] + (i & 1);
        }
        for (i = 0; i < n; i++) {
            for (j = 0; j < 1 << m; j++) {
                f[i + 1][0] = Math.max(f[i + 1][0], f[i][j]);
            }
            if (i > 0) {
                for (j = 0; j < 1 << m; j++) {
                    for (k = 0; k < 1 << m; k++) {
                        if (!((j & k) > 0) && !((a[i - 1] & k) > 0) && !((a[i] & k) > 0)) {
                            f[i + 1][k] = Math.max(f[i + 1][k], f[i][j] + o[k]);
                        }
                    }
                }
            }
            for (j = 0; j + 1 < m; j++) {
                if (!((a[i] >> j & 1) > 0) && !((a[i] >> j + 1 & 1) > 0)) {
                    for (k = 0; k < 1 << m; k++) {
                        if (!((k >> j & 1) > 0) && !((k >> j + 1 & 1) > 0)) {
                            f[i + 1][k | 1 << j | 1 << j + 1] = Math.max(f[i + 1][k | 1 << j | 1 << j + 1], f[i + 1][k] + 1);
                        }
                    }
                }
            }
        }
        for (i = 0; i < 1 << m; i++) {
            ans = Math.max(ans, f[n][i]);
        }
        return ans;
    }

    public int[] bonus(int n, int[][] leadership, int[][] operations) {
        final int MODULO = 1000000007;
        Map<Integer, List<Integer>> leadershipMap = new HashMap<>();
        int[] parents = new int[n + 1];
        for (int[] array : leadership) {
            int num1 = array[0], num2 = array[1];
            parents[num2] = num1;
            List<Integer> list = leadershipMap.getOrDefault(num1, new ArrayList<>());
            if (!list.contains(num2)) {
                list.add(num2);
                leadershipMap.put(num1, list);
            }
        }
        Queue<Integer> countQueue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        countQueue.offer(1);
        while (!countQueue.isEmpty()) {
            int num = countQueue.poll();
            stack.push(num);
            List<Integer> list = leadershipMap.getOrDefault(num, new ArrayList<>());
            for (int nextNum : list) {
                countQueue.offer(nextNum);
            }
        }
        int[] counts = new int[n + 1];
        while (!stack.isEmpty()) {
            int num = stack.pop();
            counts[num]++;
            int parent = parents[num];
            if (parent > 0) {
                counts[parent] += counts[num];
            }
        }
        int[] coinsArray = new int[n + 1];
        List<Integer> queryList = new ArrayList<>();
        for (int[] operation : operations) {
            int operationType = operation[0];
            if (operationType == 1) {
                int num = operation[1], coins = operation[2];
                while (num >= 1) {
                    coinsArray[num] += coins;
                    num = parents[num];
                }
            } else if (operationType == 2) {
                int headerNum = operation[1], coins = operation[2];
                int parentNum = parents[headerNum];
                while (parentNum >= 1) {
                    coinsArray[parentNum] += coins * counts[headerNum];
                    parentNum = parents[parentNum];
                }
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(headerNum);
                while (!queue.isEmpty()) {
                    int num = queue.poll();
                    coinsArray[num] += coins * counts[num];
                    List<Integer> list = leadershipMap.getOrDefault(num, new ArrayList<>());
                    for (int nextNum : list) {
                        queue.offer(nextNum);
                    }
                }
            } else if (operationType == 3) {
                int headerNum = operation[1];
                long queryResult = coinsArray[headerNum] % MODULO;
                int queryResultInteger = (int) queryResult;
                queryList.add(queryResultInteger);
            }
        }
        int size = queryList.size();
        int[] ret = new int[size];
        for (int i = 0; i < size; i++) {
            ret[i] = queryList.get(i);
        }
        return ret;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //针对特殊情况的优化，小于4个元素的数组是不符合题意的
        if (nums == null || nums.length < 4) {
            return res;
        }
        //先排序
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 3; i++) {
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //优化，若i的连续四数之和大于target，后面肯定没有符合题意的组合，直接跳出
            if ((nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]) > target) {
                break;
            }
            //若i和前三大的数之和都小于target，那i肯定太小，遍历下一个
            if ((nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3]) < target) {
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                //去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                //针对特殊情况优化，同上
                if ((nums[i] + nums[j] + nums[j + 1] + nums[j + 2]) > target) {
                    break;
                }
                if ((nums[i] + nums[j] + nums[len - 1] + nums[len - 2]) < target) {
                    continue;
                }
                int start = j + 1;
                int end = len - 1;
                while (start < end) {
                    int sum = nums[i] + nums[j] + nums[start] + nums[end];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
                        while (start < end && nums[start] == nums[++start]) {
                            ;
                        }
                        while (start < end && nums[end] == nums[--end]) {
                            ;
                        }
                    }
                    //当前四数之和小于target，则右移左指针
                    else if (sum < target) {
                        while (start < end && nums[start] == nums[++start]) {
                            ;
                        }
                    } else {
                        while (start < end && nums[end] == nums[--end]) {
                            ;
                        }
                    }
                }
            }
        }
        return res;
    }
}
